#include <vector>
#include <deque>


#define DEBUG_LEVEL 8
#include <debug_func.h>

//boost
#include <boost/foreach.hpp>


#include "main.h"
#include "genes_sans_orphans.h"


using std::deque;
using std::vector;



//________________________________________________________________________________________

//	eliminate_genes_without_orthologs
// 
// 		this is especially if the orthologs are on chromosomes which have
// 		 been excluded like "Un"
// 		But also after small block have been eliminated etc.
//
//________________________________________________________________________________________
void eliminate_genes_without_orthologs(const deque<deque<unsigned> >& 	ortholog_sets,
									   vector<char>&					gene_pos_to_orphan)
{
	debug_func_cout(5);
	// ortholog_set with index is a null special case: start with one
	for (unsigned i = 1; i < ortholog_sets.size(); i += 2)
	{	
		#ifndef NDEBUG
		BOOST_FOREACH(unsigned gene_pos, ortholog_sets[i])
			assert(gene_pos < gene_pos_to_orphan.size());
		BOOST_FOREACH(unsigned gene_pos, ortholog_sets[i + 1])
			assert(gene_pos < gene_pos_to_orphan.size());
		#endif

		
		unsigned cnt_sets_without_orphans = 0;
		BOOST_FOREACH(unsigned gene_pos, ortholog_sets[i])
			if (!gene_pos_to_orphan[gene_pos])
			{
				++cnt_sets_without_orphans;
				break;
			}
		BOOST_FOREACH(unsigned gene_pos, ortholog_sets[i + 1])
			if (!gene_pos_to_orphan[gene_pos])
			{
				++cnt_sets_without_orphans;
				break;
			}

		// both sets have non-orphans: fine
		if (cnt_sets_without_orphans==2)
			continue;

		// one set only has orphans or has no genes
		// set the other set to orphans
		BOOST_FOREACH(unsigned gene_pos, ortholog_sets[i])
			gene_pos_to_orphan[gene_pos] = true;
		BOOST_FOREACH(unsigned gene_pos, ortholog_sets[i + 1])
			gene_pos_to_orphan[gene_pos] = true;
	}
}


//________________________________________________________________________________________

//	set_relative_ortholog_sets

//________________________________________________________________________________________
void set_relative_ortholog_sets( const vector<unsigned>&		gene_pos_to_rel_gene_pos,
								 const deque<deque<unsigned> >&	ortholog_sets,
								 deque<deque<unsigned> >&		rel_ortholog_sets)
{
	debug_func_cout(5);
	// assign memory
	if (rel_ortholog_sets.size() != ortholog_sets.size())
		rel_ortholog_sets.assign(ortholog_sets.size(), deque<unsigned>());

	// only assign to ortholog set if not orphan
	for (unsigned ortholog_id = 0; ortholog_id < ortholog_sets.size(); ++ortholog_id)
	{
		rel_ortholog_sets[ortholog_id].clear();
		BOOST_FOREACH(unsigned gene_pos, ortholog_sets[ortholog_id])
		{
			assert(gene_pos < gene_pos_to_rel_gene_pos.size());
			assert(gene_pos_to_rel_gene_pos[gene_pos] != std::numeric_limits<unsigned>::max());
			if (gene_pos_to_rel_gene_pos[gene_pos])
				rel_ortholog_sets[ortholog_id].push_back(gene_pos_to_rel_gene_pos[gene_pos]);
		}	
	}
}
//________________________________________________________________________________________

//	set_relative_gene_positions

//________________________________________________________________________________________
void set_relative_gene_positions(const deque<deque<unsigned> >	gene_pos_by_chromosome[],
								 const vector<char>&			gene_pos_to_orphan,
								 vector<unsigned>&				gene_pos_to_rel_gene_pos,
								 deque<unsigned>&				rel_gene_pos_to_gene_pos)
{
	debug_func_cout(5);
	

	rel_gene_pos_to_gene_pos.clear();

	// a relative gene pos of 0 is for orphans
	unsigned relative_pos = 1;
	rel_gene_pos_to_gene_pos.push_back(std::numeric_limits<unsigned>::max());

	for (unsigned species_id = 0; species_id < 2; ++species_id)
	{
		#ifndef NDEBUG
		unsigned chromosome_id = 0;
		#endif
		BOOST_FOREACH(const deque<unsigned>& chromosome, gene_pos_by_chromosome[species_id])
		{
			assert(chromosome.size());
			debug_cout(5,	"species = " << species_id << ", chromosome = " <<
							chromosome_id << ", gene_pos start = " << chromosome.front() <<
							", back = " << chromosome.back());
			BOOST_FOREACH(unsigned gene_pos, chromosome)
			{
				assert(gene_pos < gene_pos_to_orphan.size());
				assert(gene_pos < gene_pos_to_rel_gene_pos.size());
				if (gene_pos_to_orphan[gene_pos])
				{
					gene_pos_to_rel_gene_pos[gene_pos] = 0;
					debug_cout(5, "orphan=>>\t" << species_id << "\t" << chromosome_id << "\t" << gene_pos);
					continue;
				}
				debug_cout(5, species_id << "\t" << chromosome_id << "\t" << gene_pos << "\t" << relative_pos);
				gene_pos_to_rel_gene_pos[gene_pos] = relative_pos;
				rel_gene_pos_to_gene_pos.push_back(gene_pos);
				++relative_pos;
			}
			// 500 between chromosomes
			relative_pos += 500;
			rel_gene_pos_to_gene_pos.insert(rel_gene_pos_to_gene_pos.end(), 500,
											std::numeric_limits<unsigned>::max());
			#ifndef NDEBUG
			++chromosome_id;
			#endif
		}

		// 500 between species just in case!!!
		relative_pos += 500;
		rel_gene_pos_to_gene_pos.insert(rel_gene_pos_to_gene_pos.end(), 500,
										std::numeric_limits<unsigned>::max());
	}
}


//________________________________________________________________________________________

//	get_gene_pos_sans_orphans

//		get gene orders with intervening orphans removed

//________________________________________________________________________________________
void get_gene_pos_sans_orphans(	const deque<deque<unsigned> >	gene_pos_by_chromosome[],
								vector<unsigned>&				gene_pos_to_rel_gene_pos,
								deque<unsigned>&				rel_gene_pos_to_gene_pos,
								const deque<deque<unsigned> >&	ortholog_sets,
								deque<deque<unsigned> >&		rel_ortholog_sets,
								vector<char>&					gene_pos_to_orphan,
								const vector<signed char>&		gene_pos_to_strand,
								vector<signed char>&			rel_gene_pos_to_strand)
{
	assert(gene_pos_to_strand.size());
	eliminate_genes_without_orthologs(ortholog_sets,
									  gene_pos_to_orphan);
	set_relative_gene_positions(gene_pos_by_chromosome, gene_pos_to_orphan,
								gene_pos_to_rel_gene_pos, rel_gene_pos_to_gene_pos);
	set_relative_ortholog_sets(gene_pos_to_rel_gene_pos, ortholog_sets, rel_ortholog_sets);
	rel_gene_pos_to_strand.assign(rel_gene_pos_to_gene_pos.size(), '\0');
	assert(rel_gene_pos_to_strand.size() == rel_gene_pos_to_gene_pos.size());
	const unsigned IGNORE = std::numeric_limits<unsigned>::max();
	for (unsigned i = 1; i < rel_gene_pos_to_gene_pos.size(); ++i)
	{
		assert(rel_gene_pos_to_gene_pos[i] == IGNORE  || 
			   rel_gene_pos_to_gene_pos[i] < gene_pos_to_strand.size());
		assert(i < rel_gene_pos_to_strand.size());
		if (rel_gene_pos_to_gene_pos[i] != IGNORE)
			rel_gene_pos_to_strand[i] = gene_pos_to_strand[rel_gene_pos_to_gene_pos[i]];
	}

	#ifndef NDEBUG
	std::cerr << "\t" << std::accumulate(gene_pos_to_orphan.begin(), 
										 gene_pos_to_orphan.end(), 0)
				<< " orphans\n";
	#endif
}

